BLS Signatures

\gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\g{\mathrm{G}} \gdef\h{\mathtt{H}} \gdef\e{\mathrm{e}}

Previously I wrote about several elliptic curve signature schemes. I did not cover pairing based ones. These allow for some great aggregation schemes. so let's cover those now.

Background

Hash to curve

Let \h_{\mathcal S} : \mathcal I → \mathcal S be a hash function mapping some input set \mathcal I to the output set \mathcal S. A superscript like \h' is used to indicate two domain separated hash functions.

Securely generating elliptic curve points from binary noise is challenging. The naive solution of multiplying by a generator is not secure, since the discrete logarithm is known. The BLS paper introduced the first solution: repeatedly trying x coordinates until a valid curve point is found. This method is generic but not constant time. Constant time methods exists but are curve specific.

Pairing curves

Let \G_1, \G_2, \G_3 be elliptic curve groups with the same scalar field \F, generators \g_1, \g_2, \g_3 and a pairing \e: \G_1 × \G_2 → \G_3.

A pairing is a function that satisfies \e(a ⋅ A, b ⋅ B) = a ⋅ b ⋅ \e(A, B) and is not the trivial solution \e(\dummyarg,\dummyarg) = 0. From this it follows that \e(A_1 + A_2, B) = \e(A_1, B) + \e(A_2, B) and other useful linear properties.

Note. The pairing is symmetrical in \G_1 and \G_2 so protocols also work with groups and pairing arguments swapped. This is useful if one group has better performance than the other.

Finding a pairing that satisfy the requirements is challenging, especially when there are additional constraints such as having large binary roots of unity in \F. Different families of solutions have been found:

Two important specific solutions are

Note. The 128 in alt_bn128 revers to the target security level, but it was since found that it is "closer to 96 or so". BLS12-381 development was in part motivated to address this and targets 128 bit security.

Signature aggregation

Like with elliptic curve protocols, the private key is a random scalar field element x ∈ \F and the public key is the private key times a generator X = x ⋅ \g_2. However, this alone is not secure in pairing cryptography due to the rogue key attack that I will explain later. We need to prove that we actually know the private key, a proof of possession. To do this compute and publish

S_X = x ⋅ \h_{\G_1}'(X)

Now anyone with (X, S_X) can verify the public key using

\e(S_X, \g_2) = \e(\h_{\G_1}'(X), X)

Details

\begin{aligned} \e(S_X, \g_2) &= \e(\h_{\G_2}'(X), X) \\ \e(x ⋅ \h_{\G_2}'(X), \g_2) &= \e(\h_{\G_2}'(X), x ⋅ \g_2) \\ x ⋅ \e(\h_{\G_2}'(X), \g_2) &= x ⋅ \e(\h_{\G_2}'(X), \g_2) \\ \end{aligned}

In the following I will assume all public keys have had their proofs of possession checked.

One signer, one message

To sign a message m, hash the message H = \h_{\G_1}(m) and the signature is S = x ⋅ H.

To verify, hash the message H = \h_{\G_1}(m) and check

\e(S, \g_2) = \e(H, X)

Details

\begin{aligned} \e(S, \g_2) &= \e(H, X) \\ \e(x ⋅ H, \g_2) &= \e(H, X) \\ x ⋅ \e(H, \g_2) &= \e(H, x ⋅ \g_2) \\ x ⋅ \e(H, \g_2) &= x ⋅ \e(H, \g_2) \\ \end{aligned}

Many signers, many messages

To aggregate many signatures, we simply sum them

S = S_1 + S_2 + S_3 + ⋯

Then to verify, we compute all the hashes for the messages H and check

\e(S, \g_2) = \e(H_1, X_1) + \e(H_2, X_2) + \e(H_3, X_3) + ⋯

Many signers, one message

In the case where all messages are the same, the verification simplifies to only two pairing operations:

\e(S, \g_2) = \e(H, X_1 + X_2 + X_3 + ⋯)

Threshold signatures

BLS signatures also allows for a threshold signature scheme. For a scheme where m out of n signatories can sign we first do a setup: Assign every signer i a unique a_i ∈ \F and pick another unique a ∈ \F that we will need soon. These values a are public. Use a distributed key generation protocol to create a random m-term polynomial P ∈ \F[X] and provide all the signers with private keys x_i = P(a_i) and public keys X_i = x_i ⋅ G_2. Also compute the verification public key X = P(a) ⋅ \g_2. This is basically Shamir's Secret Sharing scheme where each private key is a share of the private to the verification key.

Signing is as with plain BLS signatures. Given message m compute H = \h_{\G_1}(m). Each signer computes their signature S_i = x_i ⋅ H.

To aggregate the treshold, first verify the individual signatures using plain BLS verification. Take \mathcal I to be the set of indices i of valid signatures. Compute the Lagrange interpolation weights w_i ∈ \F as

w_i = \prod_{j ∈ \mathcal I \setminus \set{i}} \frac{a - a_j}{a_i - a_j}

where the j's range over all valid signatory indices except i. Compute the aggregate signature

S = \sum_{i ∈ \mathcal I} w_i ⋅ S_i

The aggregate signature S is now a valid BLS signatured for m for the verification public key S:

\e(S, \g_2) = \e(H, X)

Details

\begin{aligned} \e(S, \g_2) &= \e(H, X) \\ \e\p{\sum_{i ∈ \mathcal I} w_i ⋅ S_i, \g_2} &= \e(H, P(a) ⋅ \g_2) \\ \e\p{\sum_{i ∈ \mathcal I} w_i ⋅ x_i ⋅ H, \g_2} &= P(a) ⋅ \e(H, \g_2) \\ \p{\sum_{i ∈ \mathcal I} w_i ⋅ x_i} ⋅ \e\p{H, \g_2} &= P(a) ⋅ \e(H, \g_2) \\ \sum_{i ∈ \mathcal I} w_i ⋅ x_i &= P(a) \\ \sum_{i ∈ \mathcal I} P(a_i) ⋅ \prod_{j ∈ \mathcal I \setminus \set{i}} \frac{a - a_j}{a_i - a_j} &= P(a) \\ \end{aligned}

This final relation is the Langrange interpolation formula evaluated at a, it holds if \abs{\mathcal I} ≥ m.

Rogue key attack

The proof-of-possession is sometimes omitted. This makes the system vulnerable to the rogue key attack where an attacker can co-sign with forged signatures making it look like both attacker and one or more victims signed a message m. I'll cover the one victim case:

Given victim public key X, the attacker generates a random private key a ∈ \F and computes a rogue public key A = a ⋅ \g_2 - X. The attacker signs a message H as usual S = a ⋅ H. Now S looks like the aggregate signature of A and X on a common message H:

\e(S, \g_2) = \e(H, A) + \e(H, X)

Details

\begin{aligned} \e(S, \g_2) &= \e(H, A) + \e(H, X) \\ \e(a ⋅ H, \g_2) &= \e(H, a ⋅ \g_2 - X) + \e(H, X) \\ a ⋅ \e(H, \g_2) &= a ⋅ \e(H, \g_2) - \e(H, X) + \e(H, X) \\ a ⋅ \e(H, \g_2) &= a ⋅ \e(H, \g_2) \end{aligned}

Besides proof-of-possession that was used above, there are two other notable mitigation strategies (see Boneh, Drijvers & Neven (2018)). For the first, note that the attack requires the messages to be the same. Making sure that every signer signs a different message avoids the attack. One way of achieving this is including the public key in each message:

H = \h_{\G_1}\p{X, m}

Since this makes all messages distinct, we can no longer use the "many signers, one message" optimization. A second mitigation strategy is to modify the aggregation method. To aggregate a set of signatures \mathcal I we first compute pseudorandom constants c_i for each signer

c_i = \h_{\F}\p{X_i, \setb{X_j}{j ∈ \mathcal I}}

Note These c_i are a function of the whole set of signatories. Simplifying it to c_i = \h_{\F}(X_i) is not enough. This means each c_i will have to be recomputed everytime the set of signatories changes.

Using these c_i, we aggregate signatures as

S = \sum_{i∈\mathcal I} c_i ⋅ S_i

Signature aggregation is no longer associative. In fact, it can only be done once all signers are known. To verify the aggregate signature we use a correspondingly modified check

\e(S, \g_2) = \sum_{i∈\mathcal I} \e(H_i, c_i ⋅ X_i)

Details

\begin{aligned} \e(S, \g_2) &= \sum_{i∈\mathcal I} \e(H_i, c_i ⋅ X_i) \\ \e\p{\sum_{i∈\mathcal I} c_i ⋅ S_i, \g_2} &= \sum_{i∈\mathcal I} \e(H_i, c_i ⋅ x_i ⋅ \g_2) \\ \sum_{i∈\mathcal I} c_i ⋅ \e\p{x_i ⋅ H_i, \g_2} &= \sum_{i∈\mathcal I} c_i ⋅ x_i ⋅ \e(H_i, \g_2) \\ \sum_{i∈\mathcal I} c_i ⋅ x_i ⋅ \e\p{H_i, \g_2} &= \sum_{i∈\mathcal I} c_i ⋅ x_i ⋅ \e(H_i, \g_2) \\ \end{aligned}

This method also optimizes to two pairings in the repeated message case

\e(S, \g_2) = \e\p{H, \sum_{i∈\mathcal I} c_i ⋅ X_i}

Other gotchas

The BLS signature scheme is very linear. This enables all the useful aggregation schemes above, but also allows for a number of unexpected things. Linearity in the public key allows the rogue key attack. This is why we need proof-of-possession.

Linearity in the private key has interesting behaviour around zero. For example a zero private key produces signatures valid for all messages: S = 0 ⋅ \h_{\G_1}(m) = 0. This is mitigated by rejecting the public key 0 ⋅ \g_2. But this is not enough.

Two colluding signers pick private keys a_1 and a_2 = -a_1 and register their public keys A_1 = a_1 ⋅ \g_2 and A_2 = a_2 ⋅ \g_2. Now anyone can claim A_1 and A_2 are part of any aggregate signature with any message. Given a batch signature S = \sum_i x_i ⋅ H_i such that

\e(S, \g_2) = \sum_i \e(H_i, X_i)

Then S also verifies with A_1 and A_2 signing an arbitrary message H:

\e(S, \g_2) = \e(H, A_1) + \e(H, A_2) + \sum_i \e(H_i, X_i)

Details

\begin{aligned} \e(S, \g_2) &= \e(H, A_1) + \e(H, A_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= \e(H, a_1 ⋅ \g_2) + \e(H, a_2 ⋅ \g_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= a_1 ⋅ \e(H, \g_2) + a_2 ⋅ \e(H, \g_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= (a_1 + a_2) ⋅ \e(H, \g_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= 0 ⋅ \e(H, \g_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= \sum_i \e(H_i, X_i) \\ \end{aligned}

This generalizes to more complex linear relations among the public keys.

Linearity in the signatures can be exploited to create two signatures that are individually invalid, but their aggregate is valid. Start with two valid signatures S_1, S_2 and an arbitrary non-zero point P ∈ \G_1, then compute the two new signatures

\begin{aligned} S_1' &= S_1 + P & S_2' &= S_2 - P \end{aligned}

References

Remco Bloemen
Math & Engineering
https://2π.com